1. Field of the Invention
The present invention relates generally to cryptography and, more particularly, to public key cryptographic systems such as RSA.
2. Description of the Prior Art
With the enormous volume of data that is transmitted electronically throughout the world, methods for securing the privacy of that data are crucial to the economy. Before the 1970s, senders and recipients would need to agree on some sort of secret key in order to encrypt messages such that they could not be deciphered by unauthorized third parties but could still be read by the intended recipient. This sort of symmetric cryptography alone is inconvenient in the Internet age, where it is not always easy to arrange a meeting to exchange a secret password that will allow for future secure communications. Fortunately, public key cryptography was developed in the last few decades by Diffie, Hellman, Rivest, Shamir, and Adelman, among others.
Public key cryptography allows for the secure exchange of information between senders and recipients without the necessity that the two parties first exchange a secret key. The recipient simply makes his public key available, which can be used by anyone to encrypt a message to him. Once a message is encrypted using the recipient's public key, only the private key can be used to restore the message to its original state. Only the recipient knows his private key, so messages encrypted with the public key are secure.
The standard methods for public key cryptography were developed by Rivest, Shamir, and Adelman (RSA), described in U.S. Pat. No. 4,405,829. RSA and its variants provide for encryption of data using a public key and decryption using a private key.
RSA security has been publicly and commercially used for communicating or transmitting information, data, documents, messages, and files. However, the basic RSA model is designed for communication between one party and another. There is no notion of communication between one party and a group, such as a company. Under the current RSA model, the group would need to share its private key with all members of the group. This kind of “secret sharing” harkens back to the days of symmetric encryption, which RSA was designed to avoid. In the current environment of global collaboration, a method for group communication based on RSA public key cryptography is needed.
Before explaining the current invention, it is useful to describe the current single-party RSA system.
Single-Party RSA
RSA consists of three steps: key generation, encryption, and decryption.
Key Generation
Key generation starts by deciding on an adequate length for what is called the public modulus N. This choice is dictated by the difficulty of factoring N into its prime factors. Right now, N of length 1024 bits is considered a sufficient size to prevent factoring. The bit length of N will continue to go up in the future. Next, two random prime numbers that are each half the length of N, p and q, are generated. Next, a small odd integer, e, is selected such that e is relatively prime to lcm(p−1, q−1). In practice, e is usually chosen to be 65537. In this paper, we will refer to e as the public exponent and N as the public modulus. The RSA public key consists of the two integers (e, N).
The private exponent, d, is a multiplicative inverse of e(mod lcm(p−1, q−1)), so that e*d=1 mod (lcm(p−1, q−1)). Often, the private key refers to the set of numbers (p, q, d), so d should be referred to as the private exponent rather than as the private key.
Encryption
To encrypt message X using an RSA public key {e, N}, one must first convert X into an integer M using a formatting operation. Encryption of M into ciphertext C is then accomplished by calculating C as the remainder after N is divided into M taken to the power of e. In equation form, C=Me mod N where M is an integer greater than −1 and less than N, 0≦M<N.DecryptionTo decrypt using the original implementation of RSA, M is obtained by calculating the remainder after N is divided into C taken to the power of d.In equation form, M=Cd mod N. M is then converted back to X by reversing the same formatting operation that was used to obtain M from X originally.
In prior art, secure communication to a group required that members of the group (directly or indirectly) retain a “shared secret” with the group. This secret could be a group private key that all members shared, or it could be a symmetric key (password) that was held in common. Difficulties arose, however, in the management of cryptographic groups such as this. Because all group members shared the same secret, adding or removing members from the group often involved distributing new keys to all existing members. The extensive “re-keying” in a group environment required by prior art often created confusion and administrative inefficiency, since key management is considered perhaps the most problematic aspect of cryptography and one of the greatest barriers to its widespread adoption. Thus, there remains a need for methods and systems providing for secure communication in a group environment that permit members to leave the group while permitting remaining group members to securely use existing keys for group communication thereafter without permitting former members to decrypt the communication intended for decryption only be remaining group members.